Depth-First Search

-return to blog- • -return to wiki-

Computer Science

Depth-first Search (DFS)

Completely traverse one sub-tree before exploring a sibling sub-tree. You'll print the left bottom-most child, the parent after completing its left subtree, then continue with the right subtree. The code uses stacks, really, and recursive.


* InOrderTraversal([tree](/view/Tree))
* * if [tree](/view/Tree) = nil:
* * * return
* * InOrderTraversal([tree](/view/Tree).left)
* * print([tree](/view/Tree).key)
* * InOrderTraversal([tree](/view/Tree).right)

Or print root, left child, left child, if finished left child print right child.


* PreOrderTraversal([tree](/view/Tree)) - really [o](/view/O)nly for binary [tree](/view/Tree)
* * if [tree](/view/Tree) = nil:
* * * return
* * print([tree](/view/Tree).key)
* * PreOrderTraversal([tree](/view/Tree).left)
* * PreOrderTraversal([tree](/view/Tree).right)

Or print root last. Print left bottom most child, siblings, parent, right child of node's left bottom most child, etc.


* PostOrderTraversal([tree](/view/Tree))
* * if [tree](/view/Tree) = nil:
* * * return
* * PreOrderTraversal([tree](/view/Tree).left)
* * PreOrderTraversal([tree](/view/Tree).right)
* * print([tree](/view/Tree).key)

(ALGS201x)